package leetcode.tree;

/**
 * 给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。
 * <p>
 * 在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2h 个节点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,2,3,4,5,6]
 * 输出：true
 * 解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,2,3,4,5,null,7]
 * 输出：false
 * 解释：值为 7 的节点不满足条件「节点尽可能靠左」。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [1, 100] 内
 * 1 <= Node.val <= 1000
 * 请问您在哪类招聘中遇到此题？
 * 1/5
 * 社招
 * 校招
 * 实习
 * 未遇到
 */
public class LeetCode958_IsCompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        TreeNode[] tn = new TreeNode[1001];

        int p = 0, q = 0;
        boolean leaf = false;
        tn[q++] = root;

        while (p < q) {
            TreeNode treeNode = tn[p++];

            if (treeNode.left == null && treeNode.right != null) {
                return false;
            }

            if (leaf) {
                if (treeNode.left != null || treeNode.right != null) {
                    return false;
                }
            }
            if (treeNode.left != null) {
                tn[q++] = treeNode.left;
            }
            if (treeNode.right != null) {
                tn[q++] = treeNode.right;
            }

            if (treeNode.left == null || treeNode.right == null) {
                leaf = true;
            }
        }
        return true;
    }
}
